package com.LeeCode;

/**
 * 统计特殊四元组
 */

public class Code1995 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 6};
        System.out.println(new Code1995().countQuadruplets(nums));
    }

    public int countQuadruplets(int[] nums) {
        int count = 0;
        int n = nums.length;

        // 使用数组代替HashMap提高效率（因为数值范围有限）
        // nums[i] <= 100，所以 nums[a] + nums[b] <= 200
        int[] cnt = new int[201];

        // 从右向左遍历c的位置
        for (int c = n - 2; c >= 2; c--) {
            // 将 nums[c+1] 加入计数（作为可能的d值）
            cnt[nums[c + 1]]++;

            // 枚举a和b，计算 nums[a] + nums[b] + nums[c] 是否等于某个d
            for (int a = 0; a < c - 1; a++) {
                for (int b = a + 1; b < c; b++) {
                    int sum = nums[a] + nums[b] + nums[c];
                    if (sum <= 200) {
                        count += cnt[sum];
                    }
                }
            }
        }

        return count;
    }
}
